package com.example.demo.test.leetcode.day1203;

/**
 * 计数质数
 * 统计所有小于非负整数 n 的质数的数量。
 */
public class Solution1203 {
    public static void main(String[] args) {
        //  System.out.println(countPrimes1(0));
        System.out.println(countPrimes2(10));
    }

    public static int countPrimes1(int n) {
        if (n < 2)
            return 0;
        int count = 0;
        boolean flag = true;
        for (int i = 2; i < n; i++) {
            flag = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0)
                    flag = false;
            }
            if (flag)
                count++;
        }

        return count;
    }

    public static int countPrimes2(int n) {
        int count = 0;
        boolean[] signs = new boolean[n];
        for (int i = 2; i < n; i++) {
            // 排除i的倍数
            if (!signs[i]) {
                count++;
                for (int j = i + i; j < n; j += i)
                    signs[j] = true;
            }
        }
        return count;
    }

}
